/**
 * 309. 最佳买卖股票时机含冷冻期
 */
public class Solution_309 {
    /**
     * 官方题解：动态规划
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(N)
     */
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int len = prices.length;
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        int[][] f = new int[len][3];
        f[0][0] = -prices[0];
        for (int i = 1; i < len; ++i) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
            f[i][1] = f[i - 1][0] + prices[i];
            f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
        }
        return Math.max(f[len - 1][1], f[len - 1][2]);
    }

    public static void main(String[] args) {
        Solution_309 solution = new Solution_309();
        int[] prices = { 1, 2, 3, 0, 2 };
        int ans = solution.maxProfit(prices);
        System.out.println(ans);
    }
}
